public class ReorderList {
    public void reorderList(ListNode head) {
        // 1.找到链表的中间节点
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 2.把后面部分逆序(头插法)
        ListNode virtualNode = new ListNode();
        ListNode tmp = slow.next; //把链表分离
        slow.next = null;
        // 头插法进行逆序, 头插在虚拟节点之后
        while(tmp != null) {
            // 先连接后面的节点
            ListNode tmpNext = tmp.next;
            tmp.next = virtualNode.next;
            virtualNode.next = tmp;
            tmp = tmpNext;
        }

        // 3.合并两个链表
        ListNode cur1 = head, cur2 = virtualNode.next;
        while(cur2 != null) {
            // cur1链比较长, 如果cur2合并后为空了,说明合并完成了,不论是奇数还是偶数,画个图就明白了
            ListNode cur1Next = cur1.next, cur2Next = cur2.next;
            cur1.next = cur2;
            cur1 = cur1Next;

            cur2.next = cur1;
            cur2 = cur2Next;
        }
    }
}
